package graph.question;

import graph.GraphNode;
import graph.graphtype.NoDirectGraph;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Description
 * @Author 26233
 * @Create 2021-04-10 23:32:28
 */

// 节点之间 全部路径
public class NodePath {

    public List<List<Integer>> path(NoDirectGraph g, int p1, int p2){

        List<List<Integer>> result = new ArrayList<>();
        List<Integer> tempList = new ArrayList<>();
        int[] visited = new int[g.table.length];

        Stack<GraphNode> stack = new Stack<>();
        GraphNode tempNode;
        boolean flag;

        stack.add(g.table[p1]);

        while (!stack.isEmpty()){
            flag = true;
            tempNode = stack.pop();
            visited[tempNode.id] = 1;
            tempList.add(tempNode.id);
            if (tempNode.id == p2){
                result.add(tempList);
                break;
            }
            while (tempNode.next != null){
                if (visited[tempNode.next.id] != 1) {
                    stack.add(tempNode.next.edgeNode);
                    flag = false;
                }
                tempNode = tempNode.next;
            }

            if (flag) {
                tempList.remove(tempList.size() - 1);
            }
        }

        return result;
    }

    public List<List<Integer>> pathAll(NoDirectGraph g, int p1, int p2){

        List<List<Integer>> result = new ArrayList<>();
        List<Integer> tempList = new ArrayList<>();
        int[] visited = new int[g.table.length];

        // 栈模拟递归调用
        Stack<GraphNode> stack;
        Stack<GraphNode> tempStack = new Stack<>();
        List<Stack<GraphNode>> ls = new ArrayList<>();
        GraphNode tempNode;

        tempNode = g.table[p1];
        tempList.add(tempNode.id);
        stack = new Stack<>();
        while (tempNode.next != null) {
            if (visited[tempNode.next.id] != 1) {
                stack.add(tempNode.next.edgeNode);
            }
            tempNode = tempNode.next;
        }
        ls.add(stack);
        visited[p1] = 1;

        while(ls.size() > 0){
            tempStack = ls.get(ls.size() - 1);
            while (!tempStack.isEmpty()){
                tempNode = tempStack.pop();
                visited[tempNode.id] = 1;
                tempList.add(tempNode.id);

                if (tempNode.id == p2){
                    result.add(new ArrayList<>(tempList));
                    visited[p2] = 0;
                    tempList.remove(tempList.size() - 1);
                    continue;
                }
                stack = new Stack<>();
                while (tempNode.next != null) {
                    if (visited[tempNode.next.id] != 1) {
                        stack.add(tempNode.next.edgeNode);
                    }
                    tempNode = tempNode.next;
                }
                ls.add(stack);
                tempStack = stack;
            }
            visited[tempList.remove(tempList.size() - 1)] = 0;
            ls.remove(ls.size() - 1);
        }

        return result;
    }

    ///////////////////////递归法
    public List<List<Integer>> pathAllRecursive(NoDirectGraph g, int p1, int p2){
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> tempList = new ArrayList<>();
        int[] visited = new int[g.table.length];

        Stack<GraphNode> stack = new Stack<>();
        GraphNode tempNode = g.table[p1];
        tempList.add(tempNode.id);
        while (tempNode.next != null) {
            if (visited[tempNode.next.id] != 1) {
                stack.add(tempNode.next.edgeNode);
            }
            tempNode = tempNode.next;
        }
        visited[p1] = 1;
        pathAll(p2, visited, stack, tempList, result);
        return result;
    }

    public void pathAll(int p2, int[] visited, Stack<GraphNode> stack, List<Integer> tempList, List<List<Integer>> result){
        while(!stack.isEmpty()){
            GraphNode tempNode = stack.pop();
            visited[tempNode.id] = 1;
            tempList.add(tempNode.id);
            if (tempNode.id == p2){
                result.add(new ArrayList<>(tempList));
                visited[p2] = 0;
                tempList.remove(tempList.size() - 1);
                continue;
            }
            Stack<GraphNode> s = new Stack<>();
            while (tempNode.next != null) {
                if (visited[tempNode.next.id] != 1) {
                    s.add(tempNode.next.edgeNode);
                }
                tempNode = tempNode.next;
            }
            pathAll(p2, visited, s, tempList, result);
        }
        visited[tempList.remove(tempList.size() - 1)] = 0;
    }

    public static void main(String[] args) {
        int[][] edges = new int[][]{{0, 1}, {0, 2}, {0, 4}, {1, 0}, {1, 3}, {2, 0}, {2, 3}, {2, 4}, {3, 1}, {3, 2}, {3, 4}, {4, 0}, {4, 2}, {4, 3}};
        int[] data = new int[]{1, 2, 3, 4, 5};

        NoDirectGraph g = new NoDirectGraph(data.length, data);
        g.generateGraph(edges);

        // List<List<Integer>> path = new NodePath().path(g, 0, 1);
        // List<List<Integer>> path = new NodePath().pathAll(g, 1, 0);
        List<List<Integer>> path = new NodePath().pathAllRecursive(g, 1, 0);

        System.out.println("path = " + path);
    }

}
